/***************************************************************************************************
 *Copyright(C),2010-2016,Sumscope
 *FileName	:  pinyin_search_set.cpp
 *Author	:  scofined.qi
 *Version	:  1.0
 *Date		:  2017/11/23
 *Desc		:  //用于主要说明此程序文件完成的主要功能
 *Relation :
 *Others	:  //其他内容说明
 *Function :  //主要函数列表，每条记录应包含函数名及功能简要说明
 *History	:
 * //修改历史记录列表，每条修改记录应包含修改日期、修改者及修改内容简介
 ***************************************************************************************************/
#include "pinyin_search_set.h"

#include <core/instance/singleton.h>

#include "../../allocator/allocator_pool_manager.h"

#ifndef WIN32
#include <sys/mman.h>
#endif

#ifndef BASSERTS
#define BASSERTS  //
#endif
#ifndef BASSERT
#define BASSERT  //
#endif
#ifndef BLOGERR
#define BLOGERR  //
#endif
#ifndef BLOGINFO
#define BLOGINFO  //
#endif
#ifndef BLOGDEBUG
#define BLOGDEBUG  //
#endif

#ifndef max
#define max(a, b) ((a) > (b)) ? (a) : (b)
#endif

namespace qb {
namespace base {
namespace internal {
enum { UNIT_SIZE = 32, CACHE_COUNT = 4096 };
#define ROUND_ALIGN(NUM, SIZE) \
  ((NUM % SIZE == 0) ? NUM : ((NUM / SIZE + 1) * SIZE))
static int gs_expand_count = 0;
inline int ExpandCapcity(int capcity) {
  // 尽量是总扩展次数更少,按照128*sizeof(KeyCount)对齐
  gs_expand_count++;
  capcity += capcity < UNIT_SIZE ? UNIT_SIZE : (capcity);
  capcity = ROUND_ALIGN(capcity, InverseSetNew2::ROUND_SIZE);
  return capcity;
}
/*
        [内存优化][scofined.qi]
        一次性清理的堆
                最终通过在SpellSearchImpl::BuildIndex中调用InverseSet::Clear()
                将该堆销毁,跳过该堆分配的所有内存的一个个delege[] 阶段
        债券在建立倒排索引阶段,需要建立一个三字符到其所有债券索引数组的映射关系
        AllocArray就是分配对应的预估有ncount个债券索引的债券索引数组
        在倒排索引建立完毕之后(SpellSearchImpl::BuildIndex),所有的债券索引数组内容
        会在m_file.Update(ki.key, ki.ptr);刷新到映射文件中,然后清空内存中的
        IndexIdRange的InverseSet对象(即的m_memory_set不删除,直接设为NULL)
        最终直接销毁对应的堆句柄

        为何需要这么做:
        这些内存是大量的临时内存,临时内存对象与长期内存对象混用内存堆
        会导致内存堆出现大量内存碎片,且导致内存堆的利用率不高
        导致总的内存暴涨短时间内无法降下来
        单独用一个内存堆来管理临时内存,可以非常快速的删除大量内存而且消除内存碎片
*/
class OneHeapAllocator {
  void* m_handle;   // 堆句柄
  int m_usedsize;   // 已经使用的内存
  int m_peak_used;  // 使用的峰值
  int m_alloc_count;
  BaseString m_name;

 private:
  OneHeapAllocator() = delete;
  OneHeapAllocator(const OneHeapAllocator& heap) = delete;
  OneHeapAllocator& operator=(const OneHeapAllocator& heap) = delete;

 public:
  OneHeapAllocator(const char* name)
      : m_handle(NULL),
        m_usedsize(0),
        m_name(name ? name : ""),
        m_alloc_count(0),
        m_peak_used(0) {}
  ~OneHeapAllocator() { Reset(); }
  void Reset() {
#ifdef WIN32
    if (m_handle != NULL) {
      ::HeapDestroy(m_handle);
    }
#endif
    m_usedsize = 0;
    m_handle = NULL;
  }
  void* Alloc(int bytes) {
    void* ptr = NULL;
#ifdef WIN32
    if (m_handle == NULL) {
      m_handle = ::HeapCreate(0, 0, 0);
      if (m_handle) {
        BLOGINFO("[MEMORY][HEAP]Heap:%s HeapCreate 0x%8x", m_name.c_str(),
                 m_handle);
      }
    }
    if (m_handle) {
      ptr = ::HeapAlloc(m_handle, HEAP_ZERO_MEMORY, bytes);
    }
#else
    ptr = malloc(bytes);
#endif
    if (ptr == NULL) {
      BLOGERR("[MEMORY][HEAP]Heap:%s Alloc %6d failed, m_handle:0x%8x",
              m_name.c_str(), bytes, m_handle);
    } else {
      m_usedsize += bytes;
      m_peak_used += bytes;
      m_alloc_count++;
    }
    return ptr;
  }

  void Free(void* ptr, int bytes) {
    bool suc = false;
#ifdef WIN32
    if (m_handle && ptr) {
      suc = ::HeapFree(m_handle, 0, ptr);
    }
#else
    free(ptr);
#endif
    if (!suc) {
      BLOGERR("[MEMORY][HEAP]Heap:%s Free 0x%8x:%6d failed, m_handle:0x%8x",
              m_name.c_str(), ptr, bytes, m_handle);
    } else {
      m_usedsize -= bytes;
      m_alloc_count--;
    }
  }
  int GetBytes() const { return m_usedsize; }
#ifdef WIN32
  void DumpStatus() {
    return;
    if (m_alloc_count % 1000 == 0)
      DumpHeapStatus(false);
    else if (m_alloc_count % 100 == 0)
      BLOGDEBUG("[MEMORY][HEAP]heap:%s  0x%8x  used:%8d/%8d count:%d",
                m_name.c_str(), m_handle, m_usedsize, m_peak_used,
                m_alloc_count);
  }
  void DumpHeapStatus(bool last) {
    if (m_handle == NULL) return;
    int ncount = 0, ndata = 0, nhead = 0, nholesize = 0, ntotal = 0;
    int ndde = 0, nmove = 0, nregion = 0, nhole = 0;
    if (HeapLock(m_handle)) {
      PROCESS_HEAP_ENTRY entry = {0};
      memset(&entry, 0, sizeof(LPPROCESS_HEAP_ENTRY));
      while (HeapWalk(m_handle, &entry)) {
        ncount++;
        ntotal += entry.cbData;
        nhead += entry.cbOverhead;
        if (entry.wFlags & PROCESS_HEAP_ENTRY_DDESHARE) {
          ndde++;
          ndata += entry.cbData;
        }
        if (entry.wFlags & PROCESS_HEAP_ENTRY_MOVEABLE) {
          nmove++;
          ndata += entry.cbData;
        }
        if (entry.wFlags & PROCESS_HEAP_REGION) nregion++;
        if (entry.wFlags & PROCESS_HEAP_UNCOMMITTED_RANGE) {
          nhole++;
          nholesize += entry.cbData;
        }
        if (entry.wFlags & PROCESS_HEAP_ENTRY_BUSY &&
            entry.wFlags & PROCESS_HEAP_ENTRY_MOVEABLE) {
          BLOGINFO("[MEMORY][HEAP]Block   0x%8x %8d/%8d %8d  ptr:0x%8x",
                   entry.lpData, entry.cbData, entry.cbOverhead,
                   entry.iRegionIndex, entry.Block.hMem);
        }
        if (entry.wFlags & PROCESS_HEAP_REGION) {
          ndata += entry.Region.dwCommittedSize;
          BLOGINFO(
              "[MEMORY][HEAP]Region  0x%8x %8d/%8d %8d  ptr:0x%8x-0x%8x "
              "Commited:%d  UnCommitted:%d total:%d",
              entry.lpData, entry.cbData, entry.cbOverhead, entry.iRegionIndex,
              entry.Region.lpFirstBlock, entry.Region.lpLastBlock,
              entry.Region.dwCommittedSize, entry.Region.dwUnCommittedSize,
              entry.cbData);
        }
      }
      HeapUnlock(m_handle);
    }
    BLOGINFO(
        "[MEMORY][HEAP]Heap:%s  HeapDestroy 0x%8x  used:%8d/%8d alloc:%d "
        "count:%d data:%d/%d head:%d dde:%d move:%d region:%d hole:%d/%d",
        m_name.c_str(), m_handle, m_usedsize, m_peak_used, m_alloc_count,
        ncount, ndata, ntotal, nhead, ndde, nmove, nregion, nhole, nholesize);
  }
#endif
};
class KeyCountAllocator : public Singleton<KeyCountAllocator> {
  typedef InverseSet::KeyCount KeyCount;
  typedef HeapAllocator StdAllocator;  // 该分配器已经退化成标准c分配器
  OneHeapAllocator m_allocator;

 public:
  KeyCountAllocator() : m_allocator("PinyinSearch") {}
  void Reset() {
    m_allocator.Reset();
    BLOGINFO("[MEMORY][PREDICT]扩容次数:%6d", gs_expand_count);
  }
  KeyCount* AllocArray(int ncount) {
    return (KeyCount*)m_allocator.Alloc(ncount * sizeof(KeyCount));
  }
  void FreeArray(KeyCount* parray, int capcity) {
    // 跳过该堆分配的所有内存的一个个delege[] 阶段
    // 最终通过Reset来一次性销毁堆,因此不需要一个个释放内存
    // 因此这里不需要一个个去释放,当然去释放不会导致问题,只是浪费时间
#ifndef WIN32
    m_allocator.Free(parray, capcity);
#endif
  }
};
void InverseSetNew2::Clear() { KeyCountAllocator::instance()->Reset(); }
InverseSetNew2::InverseSetNew2()
    : m_first(0), m_count(0), m_capcity(0), m_max(1) {}
InverseSetNew2::~InverseSetNew2() {
  KeyCountAllocator::instance()->FreeArray(m_first, m_capcity);
  m_first = NULL;
}
bool InverseSetNew2::add(KeyType key) {
  int ipos = find_fast(key, 0);
  if (ipos < 0) ipos = find_slow(key, 0);
  KeyCount* pid = NULL;
  if (ipos >= 0 && ipos < m_count) {
    BASSERT(m_first != NULL);
    pid = m_first + ipos;
    if (pid->getkey() == key) {
      BASSERTS(pid->getval() < (1 << kIndexId::CountBits), "计数超限2^%d",
               kIndexId::CountBits);
      CountType val = pid->addval();
      m_max = m_max < val ? val : m_max;
      return true;
    }
  }
  // 将ipos后面的往后移动一个位置
  if (m_count >= m_capcity || ipos < 0 || m_first == NULL) {
    expand();
  }
  BASSERTS(m_first && m_count < m_capcity && m_capcity > 0, "");
  ipos = ipos < 0 ? 0 : ipos;
  if (m_count > ipos)
    memmove(&m_first[ipos + 1], &m_first[ipos],
            (m_count - ipos) * sizeof(KeyCount));
  m_first[ipos] = KeyCount(key, 1);
  m_count++;
  return true;
}

void InverseSetNew2::remove(KeyType key) {
  int ipos = find(key, 0);
  if (ipos < 0 || ipos >= m_count || m_first == NULL) return;
  KeyCount& ii = m_first[ipos];
  if (ii.getkey() != key) return;
  if (ii.getval() > 1) {
    ii.decval();
  } else {
    // 将后面的向前移动
    for (int i = ipos; i + 1 < m_count; i++) m_first[i] = m_first[i + 1];
    m_count--;
    BASSERTS(m_count >= 0, "");
  }
}
bool InverseSetNew2::exist(KeyType key) const {
  int ipos = find(key, 0);
  if (ipos >= 0 && ipos < m_count && m_first)
    return m_first[ipos].getkey() == key;
  return false;
}

void InverseSetNew2::intersect(const Base& iis) {
  // 取两个集合的并集,忽略CountType
  if (m_count <= 0 || m_first == NULL) return;
  int ncount = 0;
  for (int i = 0; i < m_count; i++) {
    if (iis.exist(m_first[i].getkey())) {
      m_first[ncount++] = m_first[i];
    }
  }
  BASSERTS(ncount <= m_count, "");
  m_count = ncount;
  if (m_capcity > m_count)
    memset(m_first + m_count, 0, (m_capcity - m_count) * sizeof(KeyCount));
}

void InverseSetNew2::check(unsigned int maxkey) {
  // 调试情况下使用
  if (m_first && m_count > 1) {
    KeyCount* last = NULL;
    for (int i = 0; i < m_count; i++) {
      //	BASSERTS(m_first[i].getkey() <= maxkey, "债券索引超限");
      //	if (last){ BASSERTS(last->getkey() < m_first[i].getkey(),
      //"严格递增检测失败"); } 	BASSERTS(m_first[i].getval() > 0 &&
      //m_first[i].getval() <= 254, "计数过大");
      last = m_first + i;
    }
  }
}
bool InverseSetNew2::get(int index, KeyType& key, CountType& val) const {
  if (index >= 0 && index < m_count && m_first) {
    key = m_first[index].getkey();
    val = m_first[index].getval();
    return true;
  }
  key = val = 0;
  return false;
}
int InverseSetNew2::find(int key, int npos) const {
  int pos = find_fast(key, npos);
  if (pos < 0) pos = find_slow(key, npos);
  return pos;
}
int InverseSetNew2::find_fast(KeyType key, int npos) const {
  if (npos < 0 || m_first == nullptr || npos >= m_count) return m_count;
  if (key <= m_first[npos].getkey()) return npos;
  if (m_count >= 1) {
    KeyType last = m_first[m_count - 1].getkey();
    if (key > last) return m_count;
    if (key == last) return m_count - 1;
  }
  return -1;
}

int InverseSetNew2::find(KeyType key, int npos) const {
  // 找到key该插入的位置
  // 所有的IndexId是按照key的大小,从小到大,严格递增排序
  int i = find_fast(key, npos);
  if (i < 0) i = find_slow(key, npos);
  if (i >= 0 && i < m_count) {
    BASSERTS(i < m_count && m_first[i].getkey() >= key,
             "i=%d m_count:%d firstkey:%d key:%d", i, m_count,
             m_first[i].getkey(), key);
    BASSERTS(i == 0 || m_first[i - 1].getkey() < key, "");
  }
  return i;
}
int InverseSetNew2::find_old(KeyType key, int npos) const {
  if (m_first == NULL) return -1;
  if (m_count >= 1) {
    KeyType last = m_first[m_count - 1].getkey();
    if (key > last) return m_count;
    if (key == last) return m_count - 1;
  }
  if (m_count <= 0 || key <= m_first[0].getkey()) return 0;
  // 已经废弃
  int left = 0, right = m_count, mid = 0;
  while (left + 4 < right) {
    mid = (left + right) >> 1;
    if (key < m_first[mid].getkey())
      right = mid;
    else
      left = mid;
  }

  int i = left;
  for (; i < right; i++) {
    if (key <= m_first[i].getkey()) break;
  }
  //	BASSERTS(i >= 0 && i < m_count, "查找债券索引失败");
  //	if (i - 1 >= 0){ BASSERTS(m_first[i - 1].getkey() < key, ""); }
  //	if (i < m_count){ BASSERTS(key <= m_first[i].getkey(), ""); }
  return i;
}
void InverseSetNew2::expand(int cap) {
  if (cap > 0 && m_capcity >= cap) return;
  if (m_first == NULL || m_count >= m_capcity || m_capcity <= 0) {
    int capcity = cap <= 0 ? ExpandCapcity(m_capcity) : (max(cap, m_capcity));
    // BLOGDEBUG("[MEMORY]InverseSetNew2 expand %6d ==> %6d  count:%d
    // sizeof(KeyCount):%4d", m_capcity, capcity, m_count, sizeof(KeyCount));
    KeyCount* buf = KeyCountAllocator::instance()->AllocArray(capcity);
    if (m_first) {
      if (m_count > 0) memcpy(buf, m_first, sizeof(KeyCount) * m_count);
      KeyCountAllocator::instance()->FreeArray(m_first, m_capcity);
    } else
      memset(buf, 0, sizeof(KeyCount) * capcity);
    m_first = buf;
    m_capcity = capcity;
  }
}
bool InverseSetNew2::shrink(int delta) {
  if (m_first && m_count > 0 && m_count + delta < m_capcity) {
    KeyCount* buf = KeyCountAllocator::instance()->AllocArray(m_count);
    memcpy(buf, m_first, sizeof(KeyCount) * m_count);
    KeyCountAllocator::instance()->FreeArray(m_first, m_capcity);
    m_first = buf;
    m_capcity = m_count;
    return true;
  }
  return false;
}
int InverseSetNew2::find_slow(KeyType k, int npos) const {
  if (m_first == nullptr) return -1;
  int i = -1;
  int left = npos, right = m_count - 1, mid = 0;
  int key = k;
  int kl, kr, km;
  int step;
  kl = m_first[left].getkey();
  kr = m_first[right].getkey();
  const int gap = 16;  // 经过大量测试,16效果最佳
  while (left + gap < right) {
    // 二分法:step = (right - left) >> 1;
    // 比例法:step = (right - left)*(key - kl)*1.0 / (kr - kl);
    // 经过测试,真实11w债券数据,比例法性能是二分法的2倍
    step = (int)(1.0 * (right - left) * (key - kl) / (kr - kl));
    mid = left + (step < 1 ? gap : step);
    km = m_first[mid].getkey();
    if (key == km) {
      i = mid;
      break;
    }
    if (key < km) {
      right = mid;
      kr = m_first[right].getkey();
    } else {
      left = mid + 1;
      kl = m_first[left].getkey();
    }
  }
  if (i < 0) {
    i = left;
    for (; i <= right; i++) {
      if (key <= (int)m_first[i].getkey()) break;
    }
  }
  BASSERT(i < m_count && (int)m_first[i].getkey() >= key);
  BASSERT(i == 0 || (int)m_first[i - 1].getkey() < key);
  return i;
}

}  // namespace internal
}  // namespace base
}  // namespace qb
